A cryptosystem is usable, for secure communication between users, only if the users may expect that a third party, called a “cryptanalyst,” is not able to break the cryptosystem. A definition of the term, “to break” the cryptosystem, comprises several different activities that the users seek to prevent the cryptanalyst from performing. Breaking a cryptosystem comprises any of the following activities: reading messages sent between the users, producing a fake identification of one user, which appears authentic to the other user, by conforming with certain authenticity criteria that is inaccessible to anyone other than the users, forging a digital signature for a message to falsely indicate that the message was sent by the apparent signer, etc.
If a cryptosystem cannot be broken, then the cryptosystem is said to be “secure.” However, making a secure cryptosystem is easier said than done: at the present time, there is no mathematical proof of the safety of any of the known and used cryptosystems if the key is significantly shorter than the message. (There is a well-known one-time pad system that is provably secure. However, because it uses a key that is as long as the message, it is frequently impractical to use.)
There are, however, relative mathematical proofs of the security of certain cryptosystems, in the sense that the security of the cryptosystem follows from an unproven but simple assumption, the assumption being widely believed to be true.
One cryptosystem is considered to be “more secure” than another, if, in the scientific community, there is a stronger belief that the underlying assumption of the first cryptosystem is true. The belief that one cryptosystem is more secure than another is usually based on an extensive body of related research. Some such bodies of research have originated with work performed hundreds of years ago. As a consequence, the long period of time during which the underlying assumption has been studied lends credence to the belief that the cryptosystem based on the underlying assumption is in fact secure.
Most of the cryptosystems used today employ a certain class of problems. That is, use of a previously known cryptosystem is based on knowledge of the solution to a problem. As a corollary, finding the (unknown) solution to the problem is a prerequisite for a cryptanalyst breaking the encryption.
A particular cryptosystem, or a message encrypted using a particular cryptosystem, is based on an individual case of the underlying problem. The general form of the cryptosystem is the same, regardless of the particular case of the problem used. However, the security of the encrypted message is determined, not only on the problem in general, but also on the particular case of the problem that was used in this instance to encrypt this message. It is understood that, if a cryptosystem based on a particular problem is used repeatedly, different cases of the problem are used for different messages.
The security of these cryptosystems is based on an assumption (not necessarily proven) that the problem upon which the encryption algorithm is based is difficult to solve in the average case. That is, while some cases are easier than others, and while there is not necessarily a finite, or ascertainable, total number of possible cases, it is at least empirically evident that, to a high probability, a randomly chosen case is sufficiently difficult to be useful for purposes, such as cryptography, that require that the case be difficult.
For instance, the commonly-used Rivest-Shamir-Adleman (RSA) cryptosystem given in Rivest et al., U.S. Pat. No., 4,405,829, “Cryptographic Communications System and Method,” employs a number that is a product of two large prime numbers. This cryptosystem is considered to be secure to the degree that it is difficult to factor a large, randomly chosen number, particularly a product of two large prime numbers.
The RSA cryptosystem encrypts a plaintext message M into a cyphertext C. The plaintext message M is initially given in terms of a number having a value between 1 and a large number n, n being the product of two large prime numbers p and q. M is encrypted to produce C as follows: M is divided into blocks, as appropriate. M, or each block thereof, is transformed, i.e., encrypted, to the ciphertext C as described by the expressionC=Me(mod n)where e is a number relatively prime to the product (p−1)(q−1). The encrypting key (public key) comprises the numbers e and n.
To decrypt the ciphertext C, a decrypted message M′ (which is expected to be identical to M) is obtained from the decryptor:M′=Cd(mod n)The decrypting key comprises the numbers d and n. The number d, known only to the holder of the decrypting key, is a multiplicative inverse ofe(mod(1 cm((p−1)(q−1))))Thus,ed=1(mod(1 cm((p−1)(q−1))))
A cryptanalyst is required to factor n to obtain d. Thus, the processes of encryption and decryption, as practiced in the RSA cryptosystem, make direct use of the factoring problem.
The security of the RSA cryptosystem and that of other previously known cryptosystems are based on the average-case difficulty of their underlying classes of problems. The difficulty of the RSA cryptosystem is limited by the fact that the ease of factoring numbers varies drastically. There are certain large numbers that, despite their size, are very easy to factor. For example, any power of 10, however great, is easy to factor. On the other hand, the product of two large prime numbers is more difficult to factor.
Therefore, the factoring problem used in the RSA cryptosystem is an example of a problem that is difficult in the worst case, but not difficult, or much less difficult, in the average case.
Moreover, since the development of the fundamental concept of public key cryptography, there have not been a large number of successful public key systems other than the popular and successful RSA cryptosystem. Therefore, other public key cryptosystems, even if they do not address the average-case/worst-case question, would be welcome additions to the field.
Presently there is no public key cryptosystem whose security is proved without any unproven assumption. For example, the security of RSA depends on the assumption that there is no efficient algorithm that finds the prime factors of a large integer m where m is generated as the product of two random primes satisfying certain conditions.
In other words, the security of the cryptosystem is reduced to the hardness of a computational problem; this computational problem is referenced as the hardness assumption of the corresponding cryptosystem. Since none of the hardness assumptions of the public key cryptosystems have been proved, many different public key cryptosystems with different hardness assumptions are useful. If one of the hardness assumptions is discovered to be false such that the credibility of the related cryptosystem is lost, another system may replace the failed cryptosystem.
A hardness assumption has an advantage if it comprises a simple, clearly stated mathematical statement that has been studied for a long time (preferably prior to the invention of the corresponding cryptosystem). Such a long history makes it more likely that the computational question described in the hardness assumption is truly difficult. Most of the known public key cryptosystems do not meet this requirement. For example, in the case of the RSA cryptosystem, the worst-case problem of factoring an integer is a clearly stated problem with a long history. However, the security of the RSA system is not reduced to this problem.
The security of the RSA cryptosystem depends on the hardness of an average case problem where the integer m to be factored is produced as the product of two random prime integers p and q. The distributions of p and q have a complicated description since certain pairs of primes p, q, for which factoring is easy are required to be excluded. The list of these exceptional cases is still growing. In this form, the problem is not a simply stated problem and has not been studied independently of the cryptosystem. This limitation of the RSA cryptosystem motivated the formulation of other public key systems, in particular public key cryptosystems, whose hardness assumptions are computational problems about lattices.
One previously known cryptosystem based on lattices has a clearly stated hardness assumption with a long history. Although this previously known cryptosystem has proven to be useful, it would be desirable to present additional improvements. This previously known cryptosystem (and other related cryptosystems) comprises very large key-sizes, making practical implementation difficult. There are other previously known cryptosystems related to lattices in which the keys are smaller. However, in these cryptosystems the hardness assumptions are not clearly stated mathematical problems with long histories.
Previously known cryptosystems are based on lattices and associated improvements comprise variants. All of these previously known cryptosystems (with a clearly stated hardness assumption with a long history) comprise key sizes of at least O(n2 log n). Another previously known lattice-based cryptosystem (not a public key system) comprises key sizes larger than O(n2 log n).
Several other previously known lattice-based public key cryptosystems comprise shorter keys, with size of O(n log n). However, the hardness assumptions of these previously known cryptosystems have no long history. Rather, the hardness assumptions were formulated together with the cryptosystem. A disadvantage of cryptosystems whose hardness assumption does not have a long history is that there is no evidence that the computational problem described in such a hardness assumption is truly difficult.
Thus, there is a need for a cryptosystem comprising shorter keys based on a hardness assumption that has been studied for a sufficiently long time. What is therefore needed is a public key cryptosystem, a computer program product, and an associated method utilizing a hard lattice with O(n log n) random bits for security. The need for such a solution has heretofore remained unsatisfied.